1. Field of the Invention
The present invention relates generally to data handling systems and, more particularly, to a system for ensuring the efficient scheduling of data cell request signals that enable accurate and timely routing of data cell packets.
2. Description of the Background Art
There is increasing interest in providing communications between disparate computer systems and even between networks of differing characteristics. Further, with the availability of very high bandwidth trunk lines, e.g., using fiber optic cables, there is increasing interest in combining traffic from a great variety of sources for transmission through a single trunk line. For wide area networks, packet switching technology is widely used where information to be transmitted is broken into packets of data which are preceded by headers containing information useful in routing. The header may also identify the source and the destination. Whether truly packet switched or not, most digital communication systems employ message formats in which there is an identifying header of some sort.
As is well known, data network usage is expanding at a great rate both in terms of private networks and also public networks such as the Internet. While transmission link bandwidths keep improving, the technology of the systems which connect the links has lagged behind. In particular, routers are needed which can keep up with the higher transmission link bandwidths. A high speed router needs to achieve three goals. First, it needs to have enough internal bandwidth to move packets between its input and output interfaces at the desired rates. Second, it needs enough packet processing power at the interfaces to forward the packets and, third, the router needs to be able to redirect the packets between possible paths at the requisite rates.
Conventional routers are bus based, that is, a high speed bus is provided which can link a single input to a single output at one time. The router with which the present invention is associated utilizes a crossbar switch type interconnection scheme between inputs and outputs.
One problem which exists in the context of packet switching via a crossbar switch is the allocation of available paths through the crossbar. As is understood by those skilled in the art, for unicast traffic, only a limited number of switch points can be utilized at any one time since a single input should not be connected to more than one output at a given time and, likewise, each output should only be connected to a single input.
Allocation of the available paths through a crossbar switch is performed by a device called an arbiter. An arbiter is so named because it resolves (arbitrates) conflicting resource demands. Such arbiters are discussed, for example, in the publication “Symmetric Crossbar Arbiters for VLSI Communication Switches,” by Yuval Tamir and Hsin-Chou Chi, IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 1, 1993 [hereinafter “Tamir and Chi (1993)”], the disclosure of which is incorporated by reference.
In order to provide high efficiency and throughput, an arbiter has to operate at very high speed in determining which of competing possibilities will be accommodated. Further, in many circumstances, the arbiter is preferably fair in the sense it does not overly favor one source or destination over another or one form of data communication over another. Given that very disparate patterns can exist in data communication demands, particularly when accommodating data originating from disparate systems, the allocation problem is not a simple one.
Of particular concern for many router system designers are the difficulties encountered in the transmission of multicast data cells. Several factors make arbitrating paths for and delivery scheduling of multicast cells more complicated than for unicast cells and, if implemented poorly, prone to unacceptable system performance. First, multicast cells from one ingress linecard and of the same priority with a request label of particular identifying characteristic (i.e., the cells are said to be “in the same flow”) typically share a queue with cells having differing labels, and can thus suffer from head-of-line blocking. Cells destined for a first set of outputs (as indicated by a “fanout” roster of outputs) can potentially block other cells destined for a second and differing set of outputs, even if the blocked cells' outputs are currently free. Second, cells with large fanouts may be substantially delayed before their destination outputs become free. While it is desirable to use the crossbar to copy cells, requiring that all such copies be delivered to their egress switch ports in the same time slot leads to unnecessary additional head-of-line blocking.
In order to alleviate these problems, many designers have implemented “fanout splitting” (also called “partial multicast”) in which cells are copied to those portions of the fanout that are free, while the remaining copies remain queued until such time as the outputs to which they are destined are no longer busy. Studies have shown that this simple technique can significantly increase multicast cell delivery performance. With fanout splitting, if the scheduler can deliver cell copies to one or more outputs, it will do so. Finally, because a given input port can deliver at most one multicast cell into the crossbar at a time, it is desirable to maximize the amount of the fanout that is cleared in one time slot. This effort is made difficult in large switches by the necessity of distributing the scheduling of the fanout over multiple scheduler chips. On one hand, it is desired that the different schedulers communicate in an attempt to schedule each cell in the smallest number of passes. On the other hand, it is desired that scheduling be pipelined (i.e., continually performed in descending order of priority) to maximize the scheduling rate, which in turn makes communication between the chips difficult, particularly when the communication is in the opposite direction to pipeline propagation. It is therefore a further desirable objective to reconcile these two competing factors.